// Package _47__省份数量 main
// @Title _47__省份数量
// @Description
// @Author  == 琳琳也叫王木木 ==  2022-02-17 11:00
// @Create  2022-02-17 11:00
package main

import "fmt"

/**
这他妈不就求岛屿数量嘛
*/
func findCircleNum(isConnected [][]int) int {
	var ans int
	N := len(isConnected)
	for i := 0; i < N; i++ {
		M := len(isConnected[i])
		for j := 0; j < M; j++ {
			if isConnected[i][j] == 1 {
				ans += visited(isConnected, i, j, N, M)
			}
		}
	}
	return ans
}

func visited(nums [][]int, i, j, n, m int) int {
	if i < 0 || j < 0 || i >= n || j >= m || nums[i][j] != 1 {
		return 0
	}
	nums[i][j] = 2
	// 感染四个方向的值
	if visited(nums, i+1, j, n, m)+visited(nums, i-1, j, n, m)+visited(nums, i, j+1, n, m)+visited(nums, i, j-1, n, m) > 1 {
		return 1
	}
	return 0
}

func findCircleNumDFS(isConnected [][]int) int {
	var ans int
	vis := make([]bool, len(isConnected))
	var dfs func(int)
	dfs = func(from int) {
		vis[from] = true
		for to, conn := range isConnected[from] {
			if conn == 1 && !vis[to] {
				dfs(to)
			}
		}
	}
	for i, v := range vis {
		if !v {
			ans++
			dfs(i)
		}
	}
	return ans
}

func main() {
	fmt.Println(findCircleNum([][]int{{1, 1, 0}, {1, 1, 0}, {0, 0, 1}}))
}
